3.5 In the Order Hierarchy in Figure 3.1, we have . . ., O(log n), O(n1/2), . . .. Show that, for integers n >16, log2 n < n1/2. Hint from calculus: Show that for all real numbers x >16, the slope of the function log2 x is less than the slope of the function x1/2. Since log2 (16) == 161/2, we conclude that for all real numbers x >16, log2 x < x1/2. | |
| View Solution | |
| << Back | Next >> |